package cn.genmer.test.security.algorithm.sort;

public class CountSort {
    public static void main(String[] args) {
//        int[] arr = {11,19,15,16,14,10,12,14,13,18};
        int[] arr = {93,90,94,95,95,99, 98};
        int[] sorted = sortTEST(arr);
        printArray(arr);
        printArray(sorted);
    }

    /**
     * 初始版本 第一次手写
     * @param arr
     */
    public static int[] sort0(int[] arr){
        int[] range = new int[10];
        int[] temp = new int[arr.length];
        // 累计数值出现的次数，累加到range数组对应下标的值上
        for (int i = 0; i < arr.length; i++) {
            range[arr[i]] += 1;
        }
        int j=0;
        for (int i = 0; i < range.length; i++) {
            int appearCount = range[i];
            if (appearCount > 0) {
                for (int k = 1; k <=appearCount; k++) {
                    temp[j++] = i;
                }
            }
        }
        return temp;

    }

    /**
     * 需要输入数值取值范围 0 to rangeSize
     * @param arr
     * @param rangeSize
     * @return
     */
    public static int[] sort(int[] arr, int rangeSize){
        int[] range = new int[rangeSize];
        int[] result = new int[arr.length];
        // 累计数值出现的次数，累加到range数组对应下标的值上
        for (int i = 0; i < arr.length; i++) {
            range[arr[i]] ++;
        }
        int j=0;
        for (int i = 0; i < range.length; i++) {
            int appearCount = range[i];
            while (appearCount -- > 0) result[j++] = i;
        }
        return result;

    }
    /**
     * 优化1 排序范围值,节省计数数组空间
     * 本来还想自动识别大小范围,最后决定不弄了,原因如下
     * 1. 本身就是确定的, 较为稠密的数据适合计数排序,不确定的也不一定有用
     * 2. 时间复杂度+N
     * @param arr
     */
    public static int[] sort1(int[] arr, int rangeStart, int rangeEnd){
        int rangeSize = rangeEnd-rangeStart+1;
        int[] range = new int[rangeSize];
        int[] result = new int[arr.length];
        // 累计数值出现的次数，累加到range数组对应下标的值上
        for (int i = 0; i < arr.length; i++) {
            // 下标映射
            int mappingIndex = arr[i]-rangeStart;
            range[mappingIndex] ++;
        }
        int j=0;
        for (int i = 0; i < range.length; i++) {
            // 统计出现的次数
            int appearCount = range[i];
            while (appearCount -- > 0) result[j++] = i+rangeStart;
        }
        return result;
    }

    /**
     * 优化2 为了算法完整性, 优化1基础上新增自动计算边界
     * @param arr
     */
    public static int[] sort2(int[] arr){

        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }

        int rangeSize = max-min+1;
        int[] range = new int[rangeSize];
        // 累计数值出现的次数，累加到range数组对应下标的值上
        for (int i = 0; i < arr.length; i++) {
            // 下标映射
            int mappingIndex = arr[i]-min;
            range[mappingIndex] ++;
        }
        int j=0;
        for (int i = 0; i < range.length; i++) {
            // 统计出现的次数
            int appearCount = range[i];
            while (appearCount -- > 0) arr[j++] = i+min;
        }
        return arr;
    }

    /**
     * 优化3 稳定的计数排序
     * @param arr
     */
    public static int[] sort3(int[] arr){

        // 确定边界
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }

        // 映射数组
        int rangeSize = max-min+1;
        int[] range = new int[rangeSize];
        int[] result = new int[arr.length];
        // 累计数值出现的次数，累加到range数组对应下标的值上
        for (int i = 0; i < arr.length; i++) {
            // 下标映射
            int mappingIndex = arr[i]-min;
            range[mappingIndex] ++;
        }

        // 【映射数组计算】在第二个下标开始，加上前面元素的和, 经过处理后的range数组, 每个值都代表了【当前下标的数值】在【排序后数组】中应该在的位置
        for (int i = 1; i < range.length; i++) {
            range[i] = range[i-1] + range[i];
        }
        for (int value: arr) {
            // 如原序列 {90，99，95，95，94}，range取值范围为90-99, min=90, max=99
            // 【映射数组】range应该是： 1 0 0 0 1 2 0 0 0 1
            // 【映射数组计算】range应该是： 1 1 1 1 2 4 4 4 4 5

            // value为90的情况，range[value-min] = range[0]对应的值1, 就代表他应该在【排序后数组】的第一位， 因为下标从0开始所以-1
            // value为90的情况， result[range[value-min]-1] ->  result[range[0]-1] ->  result[1-1] ->  result[0] = 90

            // 从range数组中得到，当前数（value）在【排序后数组】中应该在的位置，并将之复制给结果数组
            result[range[value-min]-1] = value;
            // 如果range
            range[value-min]--;
        }
        return result;
    }

    /**
     * 2022.12.03 优化3 第一次完全按照思路走下来，舒服
     * 2022.12.06 初始 通过 时间复杂度 2N+K，空间复杂度为 1
     *            优化 通过 时间复杂度 3N+K，且空间复杂度为 n（需要返回值）
     * 2022.12.07 从基数排序那得到， 简化【回写】部分代码
     * @param arr
     */
    public static int[] sortTEST(int[] arr){

        // 确定边界
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        // 映射数组
        int[] rangeArray = new int[max -min+1];
        for (int i = 0; i < arr.length; i++) {
            rangeArray[arr[i]-min]++;
        }
        // 映射数组计算
        for (int i = 1; i < rangeArray.length; i++) {
            rangeArray[i] = rangeArray[i-1] + rangeArray[i];
        }
        // 回写
        int[] result = new int[arr.length];
        for (int i = arr.length-1; i >=0; i--) {
            int value = arr[i];
            result[--rangeArray[value-min]] = value;
        }
        return result;
    }


    public static void printArray(int [] arr){
        for (int i: arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
